import functools


class Solution(object):
    def sellingWood(self, m, n, prices):
        d = {}
        for x, y, p in prices:
            d[(x, y)] = p

        @functools.cache
        def dfs(x, y):
            now_max = 0
            if (x, y) in d:
                now_max = d[(x, y)]
            for ux in range(1, x):
                now_max = max(now_max, dfs(ux, y) + dfs(x - ux, y))
            for uy in range(1, y):
                now_max = max(now_max, dfs(x, uy) + dfs(x, y - uy))
            return now_max

        return dfs(m, n)



data = Solution()
m = 3
n = 5
prices = [[1, 4, 2], [2, 2, 7], [2, 1, 3]]
print(data.sellingWood(m, n, prices))
